package com.platform.modules.alg.alglib.p21;

public class P21 {
    public String output = "";

    private int maxN = 1000;
    int r[] = new int[maxN];

    public static void swap(int[] arr, int num1, int num2) {
        int temp = arr[num1];
        arr[num1] = arr[num2];
        arr[num2] = temp;
    }

    void Sink(int k, int n) // 下沉操作
    {
        while (2 * k <= n) // 如果有左孩子
        {
            int j = 2 * k; // j 指向左孩子
            if (j < n && r[j] < r[j + 1]) // 如果有右孩子且左孩子比右孩子小
                j++;    // j 指向右孩子
            if (r[k] >= r[j]) // 比较大的孩子大
                break;    // 已满足堆
            else
                swap(r, k, j); // 与较大的孩子交换
            k = j; // k 指向交换后的新位置，继续向下比较，一直下沉到叶子
        }
    }

    void Swim(int k) // 上浮操作
    {
        while (k > 1 && r[k] > r[k / 2]) // 如果大于双亲
        {
            swap(r, k, k / 2); // 与双亲交换
            k = k / 2; // k 指向交换后的新位置，继续向上比较，一直上浮到根
        }
    }

    void CreatHeap(int n) // 构建初始堆
    {
        for (int i = n / 2; i > 0; i--) // 从最后一个分支结点 n/2 开始下沉调整为堆，直到第一个结点
            Sink(i, n);
    }

    void push(int n, int x) // 入队
    {
        r[++n] = x; // n 加 1 后，将新元素放入尾部
        Swim(n); // 最后一个元素上浮操作
    }

    void pop(int n) // 出队
    {
        output += r[1] + "\n"; // 输出堆顶
        r[1] = r[n--]; // 最后一个元素代替堆顶，n减1
        Sink(1, n); // 堆顶下沉操作
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        String[] words = line[0].split(" ");
        for (int i = 0; i < words.length; i++)
            r[i + 1] = Integer.parseInt(words[i]);
        int n = words.length;
        CreatHeap(n); // 创建初始堆
        int N = Integer.parseInt(line[1]);
        int x;

        for (int i = 0; i < N; i++) {
            String[] command = line[i + 2].split(" ");
            int commandNum = Integer.parseInt(command[0]);
            switch (commandNum) {
                case 1:
                    x = Integer.parseInt(command[1]);
                    push(n, x); // 入队
                    n = n + 1;
                    break;
                case 2:
                    pop(n); // 出队
                    n = n - 1;
                    break;
            }
        }

        return output;
    }
}



